// https://leetcode.cn/problems/n-ary-tree-level-order-traversal/

// 题干：给定一个 N 叉树，返回其节点值的层序遍历。（即从左到右，逐层遍历）。
//      树的序列化输入是用层序遍历，每组子节点都由 null 值分隔（参见示例）。

// 示例：输入：root = [1,null,3,2,4,null,5,6]
//      输出：[[1],[3,2,4],[5,6]]

// 碎语：层序遍历会用到BFS，因为是先进先出

#include <bits/stdc++.h>
using namespace std;

class Node {
public:
    int val;
    vector<Node*> children;

    Node() {}

    Node(int _val) {
        val = _val;
    }

    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};

class Solution
{
public:
    vector<vector<int>> levelOrder(Node* root)
    {
        vector<vector<int>> ret; // 记录最终结果
        queue<Node*> q; // 层序遍历需要的队列

        // 特殊情况处理，即根节点为空指针的情况
        if (root == nullptr) return ret;
        // 如果不是，则需要我们手动添加一下根节点
        q.push(root);
        while (q.size()){ // 若当层不为空
            int sz = q.size(); // 保存一下当层数量
            vector<int> tmp; // 创建一个动态数组用来保存数据

            for (int i = 0 ; i < sz ; i++){ // 遍历每一个当层结点，将其子结点入队并弹出自己
                // 弹出自己，并保存节点的数据值
                Node* t = q.front();
                q.pop();
                tmp.push_back(t->val);

                // 子节点入队
                for (const auto& node : t->children){
                    if (node != nullptr) q.push(node);
                }
            }
            ret.push_back(tmp);
        }
        
        return ret;
    }
};

int main()
{
    Solution sol;

    // 创建示例中的树结构
    Node* node1 = new Node(1);
    Node* node3 = new Node(3);
    Node* node2 = new Node(2);
    Node* node4 = new Node(4);
    Node* node5 = new Node(5);
    Node* node6 = new Node(6);

    node1->children = {node3, node2, node4};
    node3->children = {node5, node6};

    vector<vector<int>> result = sol.levelOrder(node1);

    // 输出结果
    for (const auto& vec : result) {
        cout << "[";
        for (int i = 0; i < vec.size(); ++i) {
            cout << vec[i];
            if (i < vec.size() - 1) {
                cout << ",";
            }
        }
        cout << "]" << endl;
    }

    // 释放动态分配的节点内存
    delete node1;
    delete node3;
    delete node2;
    delete node4;
    delete node5;
    delete node6;

    return 0;
}








